Kodiranje bojama

U informatici i teoriji grafova, metod kodiranja bojama efikasno pronalazi k-čvorova prostih puteva, k-čvorova ciklusa i druge podgrafove zadatog grafa koristeći algoritme verovatnoće. Ovaj metod pokazuje da se mnogi izomorfni problemi podgrafova (NP-kompletni problemi) mogu rešiti u polinomijalnom vremenu.

Teoriju i analizu metoda kodiranja bojama predložili su Noga Alon, Raphael Yuster, i Uri Zwick 1994. godine.

Vremenska složenost

Sledeći rezultati mogu biti dobijeni metodom kodiranja bojama:

• Za svaku konstantu $k$, ako graf $G=(V,E)$ sadrži prost ciklus $k$, onda se takav ciklus može naći u:
  • O($V^{\omega }$) očekivanom vremenu, ili
  • O($V^{\omega }\log V$) vremenu najgoreg slučaja, gde je $\omega$ eksponent množenja matrica.
• Za svaku konstantu $k$, i svaki graf $G=(V,E)$ koji je u nekoj netrivijalnoj familiji grafova, ako $G$ sadrži prost ciklus veličine $k$, onda se takav ciklus može naći u:
  • O($V$) očekivanom vremenu, ili
  • O($V\log V$) vremenu najgoreg slučaja.
• Ako graf $G=(V,E)$ sadrži podgraf izomorfan ograničenom stabloširinskom grafu koji ima $O(\log V)$ čvorova, onda se takav podgraf može pronaći u polinomijalnom vremenu.

Metod

Da bi se pronašao podgraf $H=(V_{H},E_{H})$ datog grafa $G=(V,E)$, gde $H$ može biti put ili ciklus, metoda kodiranja bojama počinje nasumičnim bojanjem svakog čvora grafa $G$ sa $k=|V_{H}|$ različitih boja, a zatim nalazi šarene kopije od $H$ u obojenom grafu $G$. Graf je šaren ako je svaki čvor u njemu obojen različitim bojama. Ova metoda funkcionise ponavljanjem (1) nasumičnog bojanja grafa i (2) pronalaženjem šarene kopije traženog podgrafa pa će se traženi podgraf pronaći u procesu ponavljanja.

Pretpostavimo da $H$ postaje šarena sa nekom ne-nula verovatnoćom $p$. Iz toga sledi da ako se nasumično bojanje ponavlja ${\tfrac {1}{p}}$ puta, onda se očekuje da $H$ postane šaren. Iako $p$ ima malu vrednost, pokazano je da ako $|V_{H}|=O(\log V)$, $p$ je samo polinomijalno male vrednosti. Pretpostavimo ponovi da postoji algoritam takav da, dati graf $G$ i bojanja koja označavaju svaki čvor grafa $G$ jednom od $k$ boja, nalazi šarenu kopiju $H$, ako ona postoji, za neko izvršno vreme $O(r)$. Onda je očekivano vreme nalaženja kopije $H$ u grafu $G$, ako ista postoji, iznosi $O({\tfrac {r}{p}})$.

Primer

Primer koji nalazi prost ciklus dužine $k$ u grafu $G=(V,E)$.

Nasumičnim bojanjem, svaki prost ciklus ima verovatnocu $k!/k^{k}>{\tfrac {1}{e^{k}}}$ da postane šaren, kako postoji $k^{k}$ različitih načina bojanja $k$ čvorova puta, među kojima su $k!$ šarenih pojavljivanja. Onda se algoritam (dole opisan), sa vremenom izvršavanja $O(V^{\omega })$ može koristiti da se pronađe šareni ciklus u nasumično obojanom grafu $G$. Zbog toga je potrebno $e^{k}\cdot O(V^{\omega })$ ukupnog vremena da se pronađe jednostavan ciklus dužine $k$ grafa $G$.

Algoritam za traženje šarenog ciklusa radi tako što prvo pronalazi sve parove čvorova u V koji su povezani prostim putem dužine k − 1, zatim proverava da li su svaka dva čvora povezana. Pozivanjem funkcije za bojanje $c:V\rightarrow \{1,\dots ,k\}$ da oboji graf $G$, numerišu se svi skupovi boja $\{1,\dots ,k\}$ u dva potskupa $C_{1}$, $C_{2}$ svaki veličine $k/2$. Primeti se da $V$ može biti podeljen na $V_{1}$ i $V_{2}$ shodno tome i $G_{1}$ i $G_{2}$ označavaju podgraf indukovanih $V_{1}$ i $V_{2}$ proporcijalno. Zatim se rekurzivno nalazi šareni put dužine $k/2-1$ u svakoj od $G_{1}$i $G_{2}$. Pretpostavimo da Bulove matrice $A_{1}$ i $A_{2}$ predstavljaju povezanost svakog para čvorova $G_{1}$ i $G_{2}$ šarenim putem, proporcijalno, i neka $B$ bude matrica koja opisuje susedstva između čvorova $V_{1}$ i $V_{2}$. Bulov proizvod $A_{1}BA_{2}$ daje sve parove čvorova u $V$ koji su povezani šarenim putem dužine $k-1$. Dakle, rekurzivni odnos množenja matrica je $t(k)\leq 2^{k}\cdot t(k/2)$, što obezbeđuje vreme izvršavanja $2^{O(k)}\cdot V^{\omega }\in O(V^{\omega })$.

Kako ovaj algoritam pronalazi samo krajnje tačke šarenog puta, postoji i drugi algoritam od Alona i Naora koji pronalazi šarene puteve koji mogu izgrađivati sami sebe.

Otklanjanje slučajnosti

Otklanjanje nasumičnosti kod kodiranja bojama podrazumeva nabrajanja mogućih boja grafa, takva da slučajnost kod bojanja više nije potrebna. Da bi ciljni podgraf $H$ u grafu $G$ bio otkriven, nabrajanje mora da sadrži bar jedan primer gde je $H$ šaren. Da bi se ovo postiglo, dovoljno je da se nabraja $k$-savršenih familija $F$ heš funkcija od $\{1,2,\dots ,|V|\}$ to $\{1,2,\dots ,k\}$. Po definiciji, $F$ je k-savršen za svaki podskup $S$ od $\{1,2,\dots ,|V|\}$ gde je $|S|=k$, postoji heš funkcija $h\in F$ takva da je $h:S\rightarrow \{1,2,\dots ,k\}$ savršena. Drugim rečima, mora postojati heš funkcija u $F$ koja boji bilo kojih datih $k$ čvorova sa $k$ različitih boja.

Postoji nekoliko različitih pristupa da se izgradi tako savršena heš familija:

1. Najbolju eksplicitnu konstrukciju napisali su: Moni Naor, Leonard J. Schulman i Aravind Srinivasan u kojoj se može dobiti familija veličine $e^{k}k^{O(\log k)}\log |V|$. Ovaj način ne zahteva da traženi podgraf postoji u originalnom problemu pronalaženja podgrafa.
2. Drugu eksplicitnu konstrukciju napisali su Jeanette P. Schmidt i Alan Siegel. Ovde je porodica veličine $2^{O(k)}\log ^{2}|V|$.
3. Još jedna konstrukcija se pojavljuje u originalnom dokumentu Noge Alona. Prvo se napravi k-savršena familija, koja mapira $\{1,2,\dots ,|V|\}$ do $\{1,2,\dots ,k^{2}\}$, zatim se napravi još jedna k-savršena familija koja mapira $\{1,2,\dots ,k^{2}\}$ do $\{1,2,\dots ,k\}$. U prvom koraku, moguće je konstruisati familiju sa $2n\log k$ slučajnih bitova koji su gotovo $2\log k$ mudro nezavisni i prostor potreban za generisanje tih slučajnih bitova može biti mali $k^{O(1)}\log |V|$. U drugom koraku, su Jeanette P. Schmidt i Alan Siegel pokazali da veličina takve $k$-savršene familije može biti $2^{O(k)}$. Shodno tome, komponovanjem $k$-savršene familije od oba koraka, može se dobiti $k$-savršena familija veličine $2^{O(k)}\log |V|$ koja mapira od $\{1,2,\dots ,|V|\}$ do $\{1,2,\dots ,k\}$.

Upotreba

Od skoro, kodiranje bojama privlači mnogo pažnje u polju bioinformatike. Jedan od primera je otkrivanje signalnih puteva u protein-protein interakciji. Drugi primer je da se otkrije i prebroji broj motiva u PPI. Proučavanjem oba omogućava dublje razumevanje sličnosti i razlika mnogih bioloških funkcija, procesa i struktura među organizmima.

Zbog velike količine prikupljenih podataka (o genima), potraga puteva i motiva može veoma dugo trajati. Međutim, korišćenjem kodiranja bojama, motivi ili signalni putevi sa $k=O(\log n)$ čvorova u mreži $G$ sa $n$ čvorova vertices mogu se naći veoma efikasno, u polinomijalnom vremenu. To omogućava istraživanja složenijih i većih struktura u protein-protein interakcijama. Više detalja se može pronaći.

Literatura

• Alon, N., Yuster, R., and Zwick, U. 1994. Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In Proceedings of the Twenty-Sixth Annual ACM Symposium on theory of Computing (Montreal, Quebec, Canada, May 23–25, 1994)
• Alon, N., Yuster, R., and Zwick, U. 1995. Color-coding. J. ACM 42, 4 (Jul. 1995)
• Coppersmith–Winograd Algorithm
• Naor, M., Schulman, L. J., and Srinivasan, A. 1995. Splitters and near-optimal derandomization. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (October 23–25, 1995)
• Schmidt, J. P. and Siegel, A. 1990. The spatial complexity of oblivious k-probe Hash functions. SIAM J. Comput. 19, 5 (Sep. 1990)
• Naor, J. and Naor, M. 1990. Small-bias probability spaces: efficient constructions and applications. In Proceedings of the Twenty-Second Annual ACM Symposium on theory of Computing (Baltimore, Maryland, United States, May 13–17, 1990)
• Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., and Sahinalp, S. C. 2008. Biomolecular network motif counting and discovery by color coding. Bioinformatics 24, 13 (Jul. 2008)
• Hüffner, F., Wernicke, S., and Zichner, T. 2008. Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection. Algorithmica 52, 2 (Aug. 2008)